"""
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

 

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

 

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        r = []
        node = self
        while node:
            r.append(str(node.val))
            node = node.next
        return "->".join(r)


class Solution:
    # 从头部开始K个一组反转
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        if k == 1:
            return head

        # 求链表长度
        size = 0
        tmp = head
        while tmp:
            tmp = tmp.next
            size += 1

        # 求有N个K组
        n = size // k

        # 进行N个K组反转
        cur = head
        new_head = new_tail = ListNode(0)
        for i in range(n):
            tmp = None
            tail = cur
            # 头插入法
            for _ in range(k):
                p = cur.next
                cur.next = tmp
                new_tail.next = cur
                cur = p
                tmp = new_tail.next
            new_tail = tail  # 更新尾部

        new_tail.next = cur
        head = new_head.next
        return head

    # 从尾部开始K个一组反转
    def reverseKGroup2(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        if k == 1:
            return head

        # 求链表长度
        size = 0
        tmp = head
        while tmp:
            tmp = tmp.next
            size += 1

        # 先求头部多余节点并拼接
        n = size // k
        m = size % k
        cur = head
        new_head = new_tail = ListNode(0)
        new_tail.next = cur
        for _ in range(m - 1):
            cur = cur.next
        new_tail = cur  # 更新尾节点
        p = cur.next
        cur.next = None  # 断开
        cur = p

        # 进行N个K组反转
        for i in range(n):
            tmp = new_tail.next
            tail = cur
            # 头插入法
            for _ in range(k):
                p = cur.next
                cur.next = tmp
                new_tail.next = cur
                cur = p
                tmp = new_tail.next
            new_tail = tail  # 更新尾部

        # new_tail.next = cur
        head = new_head.next
        return head

    # 从头部开始K个一组反转（锻炼法）
    def reverseKGroup3(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None

        if k == 1:
            return head

        # 求链表长度
        size = 0
        tmp = head
        while tmp:
            tmp = tmp.next
            size += 1

        # 求有N个K组
        n = size // k

        # 进行N个K组反转
        new_head = new_tail = ListNode(0)
        for i in range(n):
            tail = head  # 保存尾部
            for _ in range(k - 1):  # 求K长度链表
                head = head.next
            tmp = head.next  # 保存下一个节点
            head.next = None  # 断开
            new_tail.next = self.reverse(tail)  # 尾部拼接
            new_tail = tail  # 更新尾部
            head = tmp  # 更新头部
        new_tail.next = head
        head = new_head.next
        return head

    # 从尾部开始K个一组反转
    def reverseKGroup4(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        if k == 1:
            return head

        # 求链表长度
        size = 0
        tmp = head
        while tmp:
            tmp = tmp.next
            size += 1

        # 先求头部多余节点并拼接
        n = size // k
        m = size % k
        cur = head
        new_head = new_tail = ListNode(0)
        new_tail.next = cur
        for _ in range(m - 1):
            cur = cur.next
        new_tail = cur  # 更新尾节点
        p = cur.next
        cur.next = None  # 断开
        cur = p

        # 进行N个K组反转
        for i in range(n):
            tail = cur  # 保存尾部
            for _ in range(k - 1):  # 求K长度链表
                cur = cur.next
            tmp = cur.next  # 保存下一个节点
            cur.next = None  # 断开
            new_tail.next = self.reverse(tail)  # 尾部拼接
            new_tail = tail  # 更新尾部
            cur = tmp  # 更新头部

        head = new_head.next
        return head

    def reverse(self, cur):
        pre = None
        while cur:
            cur.next, cur, pre = pre, cur.next, cur
        return pre



if __name__ == '__main__':
    tree = ListNode(1)
    tree.next = ListNode(2)
    tree.next.next = ListNode(3)
    tree.next.next.next = ListNode(4)
    tree.next.next.next.next = ListNode(5)
    tree1 = ListNode(1)
    tree1.next = ListNode(2)
    tree1.next.next = ListNode(3)
    tree1.next.next.next = ListNode(4)
    tree1.next.next.next.next = ListNode(5)
    s = Solution()
    print(s.reverseKGroup(tree, 2))
    print('tree1:', tree1)
    print(s.reverseKGroup2(tree1, 2))
    print('tree1:', tree1)
    tree1 = s.reverseKGroup3(tree1, 3)
    print(tree1)
    print('tree1:', tree1)
    print(s.reverseKGroup4(tree1, 3))
    print(tree1)
